1. Field of the Invention
This invention relates generally to the processing of instructions in digital computer systems. More specifically, it relates to reduced instruction set computer (RISC) systems which use dynamic branch address tables to execute branch instructions.
2. Background Information
Control instructions are included in the instruction set architectures of processors to provide for the proper sequencing of instructions in a program, so that the programmed task can be performed correctly and efficiently. One important kind of control instruction is the branch instruction. The branch instruction changes the standard sequential order in which instructions in a program are executed. Branches may be conditional or unconditional. Conditional branches are taken when a specified condition has been satisfied, usually relating to the execution of the immediately preceding instruction. Unconditional branches are changes in program control that are always taken, without considering any conditions. When a processor executes a branch instruction, it typically transfers control to a branch target address referenced by the branch instruction. This branch target address is the address of an instruction to be executed rather than the next sequential instruction.
Most early branch instruction designs only allowed for the specification of branch target addresses that were within a set number of instructions from the current instruction. That is, the branch target address was really a relative offset, either forward or backward, from the current instruction. The size of the branch offset was bound by the number of bits allocated in the branch instruction word. To avoid this limitation, instructions known as "jumps" were used. A jump instruction changed the execution sequence of a program by setting the program counter to the specified address. This alleviated the problem of limited branch target addresses. However, it was necessary for the target address to be determined at the time the program was assembled.
This approach was not sufficiently flexible for some applications. Branch address tables were devised to provide more flexibility to the assembly language programmer in determining the desired target addresses for branch instructions. A branch address table contains a set of branch target addresses. These addresses are fixed at assembly time to point to blocks of instructions known as subroutines. Program control can be changed via one of the addresses in the branch address table by selecting an entry in the table during execution of the branch instruction. In this way, the number of possible branch target addresses is expanded.
A system using a branch address table is described in U.S. Pat. No. 5,203,006, issued to Taniai. This prior art system uses a fixed branch address table, loaded at assembly time, to reduce the number of instructions used in changing program control for a direct memory access controller. The limitations of this system include a limited number of addresses in the table, the use of only one table, the use of direct indexing into the table, and the inflexible nature of the implementation due to the use of programmable logic arrays. In addition, in the Taniai system all branch instructions must use the branch address table. No non-table branching was possible.
A branch instruction that avoids these limitations yet enlarges the number of possible branch target addresses in the branch address table and provides the capability of changing the contents of the branch address table during run-time is needed. Such an instruction would provide the maximum flexibility in selecting branch target addresses. Furthermore, a dynamic branching mechanism is needed that uses a table to change program control in only one instruction. A typical scheme using a "lookup" table to obtain the branch address takes at least four instructions after evaluation of the branch condition: a mask operation, a merge operation, a read of the table location, and a read of the entry in the table. A single comprehensive table branch instruction providing this functionality would increase processing throughput while saving space in for program storage.